class Node(object):
    def __init__(self, data=None, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

    @staticmethod
    def parent(tree, node):
        if tree is node:
            return None

        if tree.left is node or tree.right is node:
            return node

        Node.parent(tree.left, node)
        Node.parent(tree.right, node)


class RBT(object):

    @staticmethod
    def leftRotate(tree, node, parent=None):
        y = node.right
        node.right = y.left
        y.left = node
        if parent is None:
            tree = y
        if parent.left is node:
            parent.left = y
        if parent.right is node:
            parent.right = y
        return tree

    @staticmethod
    def rightRotate(tree, node, parent=None):
        x = node.left
        node.left = x.right
        x.right = node
        if parent is None:
            tree = x
            return tree
        if parent.left is node:
            parent.left = x
        if parent.right is node:
            parent.right = x
        return tree

    @staticmethod
    def insert(tree, node):
        pass

    @staticmethod
    def delete(tree, node):
        pass


if __name__ == '__main__':
    tree = Node(80, Node(40), Node(120, Node(100, Node(90), Node(110)), Node(140)))
    # RBT.leftRotate(tree, tree.right, tree) # 对120左旋
    # RBT.rightRotate(tree, tree.right, tree)  # 对120右旋
    RBT.rightRotate(tree, tree)
    print(tree.__dict__)
